{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Special Quadruplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countQuadruplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计特殊四元组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>下标从 0 开始</strong> 的整数数组 <code>nums</code> ，返回满足下述条件的 <strong>不同</strong> 四元组 <code>(a, b, c, d)</code> 的 <strong>数目</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums[a] + nums[b] + nums[c] == nums[d]</code> ，且</li>\n",
    "\t<li><code>a &lt; b &lt; c &lt; d</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3,6]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,3,6,4,5]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>[3,3,6,4,5] 中不存在满足要求的四元组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1,1,3,5]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>满足要求的 4 个四元组如下：\n",
    "- (0, 1, 2, 3): 1 + 1 + 1 == 3\n",
    "- (0, 1, 3, 4): 1 + 1 + 3 == 5\n",
    "- (0, 2, 3, 4): 1 + 1 + 3 == 5\n",
    "- (1, 2, 3, 4): 1 + 1 + 3 == 5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>4 &lt;= nums.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-special-quadruplets](https://leetcode.cn/problems/count-special-quadruplets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-special-quadruplets](https://leetcode.cn/problems/count-special-quadruplets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,6]', '[3,3,6,4,5]', '[1,1,1,3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        from sortedcontainers import SortedList\n",
    "        res = 0\n",
    "        lefts = SortedList(nums[:1])\n",
    "        for m1, nm1 in enumerate(nums[1:-2], 1):\n",
    "            nRights = nums[-1]>nm1\n",
    "            for m2 in range(N-2, m1, -1):\n",
    "                nm2 = nums[m2]\n",
    "                if nm2 > nm1:\n",
    "                    nRights += 1\n",
    "                    continue\n",
    "                res += nRights * lefts.bisect_right(nm2)\n",
    "            lefts.add(nm1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        l = []\n",
    "        dp = {}\n",
    "        ret = 0\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            p = bisect.bisect_left(l, n)\n",
    "\n",
    "            for i in range(p):\n",
    "                ret += dp[l[i]][2]\n",
    "\n",
    "            for i in range(p, len(l)):\n",
    "                dpi = dp[l[i]]\n",
    "                dpi[2] += bisect.bisect_left(dpi[1], n)\n",
    "\n",
    "            dp[n] = [1, l[:p], 0]\n",
    "            l.insert(p, n)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        sl = SortedList()\n",
    "        cnts = Counter()\n",
    "        \n",
    "        dct = defaultdict(SortedList)\n",
    "\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            for k, v in cnts.items():\n",
    "                if x > k:\n",
    "                    ans += v\n",
    "                    \n",
    "            for k, v in dct.items():\n",
    "                if k > x:\n",
    "                    cnts[k] += v.bisect_right(x)\n",
    "            \n",
    "            for y in sl:\n",
    "                if y > x:\n",
    "                    break\n",
    "                dct[x].add(y)\n",
    "            \n",
    "            sl.add(x)\n",
    "            \n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "      \n",
    "        n=len(nums)\n",
    "        presmall=[[] for _ in range(n)]\n",
    "        pre=[nums[0]]\n",
    "        for i in range(1,n):\n",
    "            index=bisect.bisect_left(pre,nums[i])\n",
    "            presmall[i]=pre[:index]\n",
    "            bisect.insort(pre,nums[i])\n",
    "        afterbig=[[] for _ in range(n)]\n",
    "        after=[nums[n-1]]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            index=bisect.bisect_left(after,nums[i])\n",
    "            if index<len(after):\n",
    "                afterbig[i]=after[index:]            \n",
    "            bisect.insort(after,nums[i])\n",
    "        res=0\n",
    "        # jk=[]\n",
    "        for j in range(n):\n",
    "            for k in range(j+1,n):\n",
    "                if nums[j]>nums[k]:\n",
    "                    index=bisect.bisect_left(presmall[j],nums[k])\n",
    "                    if index>0:\n",
    "                        lndex=bisect.bisect_left(afterbig[k],nums[j])\n",
    "                        res+=index*(len(afterbig[k])-lndex)                           \n",
    "                    # jk.append((j,k))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        left = SortedList()\n",
    "        left.add(nums[0])\n",
    "        rrr = [0]*n\n",
    "        right = SortedList()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            right.add(nums[i])\n",
    "            rrr[i] = right.copy()\n",
    "        for i in range(1,n-2):\n",
    "            for j in range(n-2,i,-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    res += left.bisect_left(nums[j])*(len(rrr[j])-rrr[j].bisect_right(nums[i]))\n",
    "            left.add(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = sortedcontainers.SortedList()\n",
    "        s.add(nums[0])\n",
    "        sl = defaultdict(sortedcontainers.SortedList)\n",
    "        for j in range(n - 2, 1, -1):\n",
    "            sl[j] = sl[j + 1].copy()\n",
    "            sl[j].add(nums[j+1])\n",
    "        # print(sl)\n",
    "        ans = 0\n",
    "        for j in range(1, n - 2):\n",
    "            for k in range(j + 1, n - 1):\n",
    "                if nums[k] < nums[j]:\n",
    "                    i = s.bisect(nums[k])\n",
    "                    l = sl[k].bisect(nums[j])\n",
    "                    ans += i * (len(sl[k]) - l)\n",
    "                    # print(j, k, s, sl, i, l, ans)\n",
    "            s.add(nums[j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = [sorted(nums[:i + 1]) for i in range(n)]  # prefix[i]: sorted(nums[:i + 1])\n",
    "        suffix = [sorted(nums[i:]) for i in range(n)]  # suffix[i]: sorted(nums[i:])\n",
    "        \n",
    "        ans = 0\n",
    "        # 遍历满足nums[j] > nums[k]的(j, k)二元组\n",
    "        for j in range(1, n - 2):\n",
    "            for k in range(j + 1, n - 1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    tmp1 = bisect_left(prefix[j - 1], nums[k])  # prefix[j - 1]中有多少个数小于nums[k]\n",
    "                    tmp2 = n - (k + 1) - bisect_left(suffix[k + 1], nums[j])  # suffix[k + 1]中有多少个数大于nums[j]\n",
    "                    ans += tmp1 * tmp2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        # nums = sorted(range(4000), key = lambda x: random.random())\n",
    "        def sortedprefix(ls):\n",
    "            cur = []\n",
    "            res = [cur]\n",
    "            for i in ls:\n",
    "                cur = cur.copy()\n",
    "                bisect.insort(cur, i)\n",
    "                res.append(cur)\n",
    "            return res\n",
    "        L = sortedprefix(nums)\n",
    "        R = sortedprefix(reversed(nums))\n",
    "        R.reverse()\n",
    "        N = len(nums)\n",
    "        res = 0\n",
    "        for k in range(N):\n",
    "            for j in range(k):\n",
    "                if nums[k]<nums[j]:\n",
    "                    # i<j, l>k, nums[i]<nums[k], nums[]\n",
    "                    icount = bisect.bisect(L[j], nums[k])\n",
    "                    lcount = len(R[k]) - bisect.bisect(R[k], nums[j])\n",
    "                    res += icount*lcount\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        s1 = [[]]\n",
    "        s2 = [[]]\n",
    "        for j in range(1,n):\n",
    "            s1.append(sorted(nums[:j]))\n",
    "        for j in range(n-1,-1,-1):\n",
    "            s2.append(sorted(nums[j:]))\n",
    "        # print(s1,s2)\n",
    "        for j in range(1,n):\n",
    "            for k in range(j+1,n-1):\n",
    "                if nums[k] < nums[j]:\n",
    "                    x = bisect.bisect(s1[j],nums[k])\n",
    "                    y = len(s2[n-k-1]) - bisect.bisect(s2[n-k-1], nums[j])\n",
    "                    # print(j,k)\n",
    "                    ans += x*y\n",
    "                    # print(x,y)\n",
    "        return ans\n",
    "                    \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        note1 = [[0] * n for _ in range(n)]\n",
    "        for k in range(2, n-1):\n",
    "            cnt = sum(nums[k] > nums[i] for i in range(k))\n",
    "            for j in range(k-1, 0, -1):\n",
    "                if nums[j] > nums[k]: note1[j][k] = cnt\n",
    "                else: cnt -= 1\n",
    "                    \n",
    "        ans = 0      \n",
    "        for j in range(1, n-2):\n",
    "            cnt = sum(nums[l] > nums[j] for l in range(j+1, n))\n",
    "            for k in range(j+1, n-1):\n",
    "                if nums[j] > nums[k]: \n",
    "                    ans += cnt * note1[j][k] \n",
    "                else: \n",
    "                    cnt -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef countQuadruplets(self, nums: List[int]) -> int:\n",
    "\t\tn=len(nums)\n",
    "\t\tijks=[[0 for i in range(n)] for j in range(n)]\n",
    "\t\tfor k in range(n):\n",
    "\t\t\tpre_sum=0\n",
    "\t\t\tfor j in range(k):\n",
    "\t\t\t\tif nums[j] > nums[k]:\n",
    "\t\t\t\t\tijks[j][k]=pre_sum\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tpre_sum+=1\n",
    "\t\tans=0\n",
    "\t\tfor j in range(n):\n",
    "\t\t\tsuf_sum=0\n",
    "\t\t\tfor k in range(n-1-j):\n",
    "\t\t\t\tif nums[n-1-k] > nums[j]:\n",
    "\t\t\t\t\tsuf_sum+=1\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tans+=ijks[j][n-1-k]*suf_sum\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        left = [[]]\n",
    "        for i in range(1, len(nums)):\n",
    "            left.append(sorted(left[-1] + [nums[i - 1]]))\n",
    "        right = [[]]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            right.append(sorted(right[-1] + [nums[i + 1]]))\n",
    "        right = right[::-1]\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums) - 2):\n",
    "            for j in range(i + 1, len(nums) - 1):\n",
    "                if nums[i] < nums[j]: continue\n",
    "                l = bisect_right(left[i], nums[j])\n",
    "                r = len(right[j]) - bisect_right(right[j], nums[i])\n",
    "                ans += l * r\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        had = [[0] * n for _ in range(n)]\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    pre[i] += 1\n",
    "\n",
    "            suf[i] = (n - nums[i]) - (i - pre[i])         \n",
    "\n",
    "        for k in range(n-1):\n",
    "            less_k = 0\n",
    "            for j in range(k-1, 0, -1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    p1 = pre[k] - less_k\n",
    "                    had[j][k] = pre[k] - less_k\n",
    "                else:\n",
    "                    less_k += 1\n",
    "\n",
    "        ans = 0\n",
    "        for j in range(n-3, 0, -1):\n",
    "            large_j = 0\n",
    "            \n",
    "            for k in range(j+1, n-1):\n",
    "                if nums[k] < nums[j]:\n",
    "                    ans += had[j][k] * (suf[j] - large_j)\n",
    "                else:\n",
    "                    large_j += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Solution:\n",
    "\tdef countQuadruplets(self, nums):\n",
    "\t\tn = len(nums)\n",
    "\t\tloc = {num: i for i, num in enumerate(nums)}\n",
    "\t\tans = 0\n",
    "\t\tleft = [[0] * n for _ in range(n)]\n",
    "\t\tss = SortedSet(range(1, n + 1))\n",
    "\t\tss.remove(nums[0])\n",
    "\t\tfor i in range(1, n - 2):\n",
    "\t\t\tss.remove(nums[i])\n",
    "\t\t\tlast = 0\n",
    "\t\t\tcnt = 0\n",
    "\t\t\tfor num in ss:\n",
    "\t\t\t\tcnt += num - last - 1\n",
    "\t\t\t\tlast = num\n",
    "\t\t\t\tif num > nums[i]:\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tleft[i][loc[num]] = cnt\n",
    "\t\tss = SortedSet(range(-n, 0))\n",
    "\t\tss.remove(-nums[-1])\n",
    "\t\tfor i in range(n - 2, 1, -1):\n",
    "\t\t\tss.remove(-nums[i])\n",
    "\t\t\tlast = n + 1\n",
    "\t\t\tcnt = 0\n",
    "\t\t\tfor num in ss:\n",
    "\t\t\t\tcnt += last + num - 1\n",
    "\t\t\t\tlast = -num\n",
    "\t\t\t\tif -num < nums[i]:\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tans += left[loc[-num]][i] * cnt\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def countQuadruplets(self, nums: List[int]) -> int:  \n",
    "        n = len(nums)  \n",
    "        z = [[0] * n for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            t = 0\n",
    "            for j in range(n-1, i, -1):\n",
    "                z[i][j] = t\n",
    "                if nums[j] > x:\n",
    "                    t += 1\n",
    "        r = 0\n",
    "        for j in range(n):\n",
    "            x = nums[j]\n",
    "            t = 0\n",
    "            for i in range(j):\n",
    "                if nums[i] > nums[j]:\n",
    "                    r += t * z[i][j]\n",
    "                if nums[i] < x:\n",
    "                    t += 1\n",
    "        return r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        def print_table(table,name=\"\"):\n",
    "            print(\"=\"*40)\n",
    "            print(name)\n",
    "            for val in reversed(range(1,n+1)):\n",
    "                print(val,end=\": \")\n",
    "                for idx in range(n):\n",
    "                    print(table[idx, val],end=\", \")\n",
    "                print()\n",
    "            print(end=\" \"*2)\n",
    "            for idx in range(n):\n",
    "                print(\"[%d]\"%idx,end=\"\")\n",
    "            print()\n",
    "\n",
    "        _DEBUG=False\n",
    "        n = len(nums)\n",
    "        myint = np.intp\n",
    "        ans = 0\n",
    "        \n",
    "        pre_le_idx_val = np.zeros(shape=(n,n+2),dtype=myint)\n",
    "        for idx in range(1,n):\n",
    "            pre_le_idx_val[idx] = pre_le_idx_val[idx-1]\n",
    "            val = nums[idx-1]\n",
    "            pre_le_idx_val[idx, val+1:n+1] += 1\n",
    "        if _DEBUG:\n",
    "            print_table(pre_le_idx_val,\"pre\")\n",
    "\n",
    "        next_ge_idx_val = np.zeros(shape=(n,n+2),dtype=myint)\n",
    "        for idx in reversed(range(0,n-1)):\n",
    "            next_ge_idx_val[idx] = next_ge_idx_val[idx+1]\n",
    "            val = nums[idx+1]\n",
    "            next_ge_idx_val[idx, 1:val] += 1\n",
    "        if _DEBUG:\n",
    "            print_table(next_ge_idx_val,\"next\")\n",
    "        \n",
    "        ans = sum(\n",
    "            pre_le_idx_val[j, nums[k]] * next_ge_idx_val[k, nums[j]] \n",
    "            # pre_le_idx_val[j, nums[k]] * (n-nums[j]-(k-1-pre_le_idx_val[k, nums[j]]))\n",
    "            for k in range(2,n)\n",
    "            for j in range(1,k) \n",
    "            if nums[k] < nums[j]\n",
    "        )\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        left = [[0 for i in range(len(nums) + 1)] for i in range(len(nums) + 1)]\n",
    "        exist = [False] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            cnt = 0\n",
    "            exist[nums[i]] = True\n",
    "            for j in range(1, nums[i]):\n",
    "                left[nums[i]][j] = cnt\n",
    "                cnt += exist[j]\n",
    "\n",
    "        exist = [False] * (len(nums) + 1)\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            exist[nums[i]] = True\n",
    "            right = [0] * (len(nums) + 1)\n",
    "            for j in range(len(nums), nums[i], -1):\n",
    "                right[j] = cnt\n",
    "                cnt += exist[j]\n",
    "            for j in range(i):\n",
    "                if nums[j] > nums[i]:\n",
    "                    ans += left[nums[j]][nums[i]] * right[nums[j]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        m1 = [[0] * n for _ in range(n)]\n",
    "        for j in range(1, n-2):\n",
    "            cnt = 0\n",
    "            for l in range(j+1, n):\n",
    "                if nums[l] > nums[j]:\n",
    "                    cnt += 1\n",
    "            for k in range(j+1, n-1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    m1[j][k] = cnt\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "        \n",
    "        m2 = [[0] * n for _ in range(n)]\n",
    "        for k in range(2, n-1):\n",
    "            cnt = 0\n",
    "            for i in range(k):\n",
    "                if nums[i] < nums[k]:\n",
    "                    cnt += 1\n",
    "            for j in range(k-1, 0, -1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    m2[j][k] = cnt\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "        \n",
    "        for x in range(1, n-2):\n",
    "            for y in range(x+1, n-1):\n",
    "                res += m1[x][y] * m2[x][y]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        p = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                p[i][j+1] = p[i][j]\n",
    "                if nums[j] < nums[i]:\n",
    "                    p[i][j+1] += + 1\n",
    "            for j in range(n-1, i, -1):\n",
    "                p[i][j-1] = p[i][j]\n",
    "                if nums[j] > nums[i]:\n",
    "                    p[i][j-1] += 1\n",
    "        \n",
    "        #print(p)\n",
    "        ans = 0\n",
    "        for i in range(1, n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    ans += p[j][i] * p[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [[0]*(n+1) for _ in range(n+1)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]: cnt += 1\n",
    "                s[i][j] = cnt\n",
    "            cnt = 0\n",
    "            for j in range(n-1, i, -1):\n",
    "                if nums[j] > nums[i]: cnt += 1\n",
    "                s[i][j] = cnt\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    ans += s[j][i-1] * s[i][j+1]\n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        lessDict = defaultdict(list)\n",
    "        for i in range(N):\n",
    "            v = nums[i]\n",
    "            count = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < v:\n",
    "                    count += 1\n",
    "                lessDict[v].append(count)\n",
    "        moreDict = defaultdict(list)\n",
    "        for i in range(N-1, -1, -1):\n",
    "            v = nums[i]\n",
    "            count = 0\n",
    "            for j in range(N-1, i, -1):\n",
    "                if nums[j] > v:\n",
    "                    count += 1\n",
    "                moreDict[v].append(count)\n",
    "        # print(moreDict, lessDict)\n",
    "        rst = 0\n",
    "        for i in range(1, N-2):\n",
    "            for j in range(i+1, N-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    arr1 = lessDict[nums[j]]\n",
    "                    arr2 = moreDict[nums[i]]\n",
    "                    if len(arr1) >= i and len(arr2) >= N-j-1:\n",
    "                        rst += arr1[i-1]*arr2[N-j-2]\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        less_cnt = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                if j:\n",
    "                    less_cnt[i][j] = less_cnt[i][j - 1]\n",
    "                if nums[i] > nums[j]:\n",
    "                    less_cnt[i][j] += 1\n",
    "        \n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            has = 0\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] < nums[i]:\n",
    "                    has += less_cnt[j][i]\n",
    "                else:\n",
    "                    result += has\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        great = [0] * n\n",
    "        great[-1] = [0] * (n + 1)\n",
    "\n",
    "        for k in range(n-2, 0, -1):\n",
    "            great[k] = great[k+1][:]\n",
    "            for x in range(1, nums[k+1]):\n",
    "                great[k][x] += 1\n",
    "        \n",
    "        less = [0] * (n + 1)\n",
    "        res = 0\n",
    "        for j in range(1, n-1):\n",
    "            for x in range(nums[j-1]+1, n+1):\n",
    "                less[x] += 1\n",
    "            for k in range(j+1, n-1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    res += less[nums[k]] * great[k][nums[j]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        r = 0\n",
    "        for t in itertools.combinations(nums, 4):\n",
    "            if sum(t[:3]) == t[3]:\n",
    "                r += 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        cnt = Counter()\n",
    "        cnt[nums[0] + nums[1]] = 1\n",
    "\n",
    "        for c in range(2, n):\n",
    "            for d in range(c+1, n):\n",
    "                if nums[d] - nums[c] in cnt:\n",
    "                    ans += cnt[nums[d] - nums[c]]\n",
    "            for i in range(c):\n",
    "                cnt[nums[i] + nums[c]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        count=0\n",
    "        for a in range(n-3):\n",
    "            for b in range(a+1,n-2):\n",
    "                for c in range(b+1,n-1):\n",
    "                    for d in range(c+1,n):\n",
    "                        if nums[a]+nums[b]+nums[c]==nums[d]:\n",
    "                            count+=1\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for b in range(n - 3, 0, -1):\n",
    "            for d in range(b + 2, n):\n",
    "                cnt[nums[d] - nums[b + 1]] += 1\n",
    "            for a in range(b):\n",
    "                if (total := nums[a] + nums[b]) in cnt:\n",
    "                    ans += cnt[total]\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/count-special-quadruplets/solutions/1179031/tong-ji-te-shu-si-yuan-zu-by-leetcode-so-50e2/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for b in range(n - 3, 0, -1):\n",
    "            for d in range(b + 2, n):\n",
    "                cnt[nums[d] - nums[b + 1]] += 1\n",
    "            for a in range(b):\n",
    "                if (total := nums[a] + nums[b]) in cnt:\n",
    "                    ans += cnt[total]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    lst = sorted(nums[c:])\n",
    "                    for d in lst:\n",
    "                        if nums[a] + nums[b] + nums[c] < d:\n",
    "                            break\n",
    "                        elif nums[a] + nums[b] + nums[c] == d:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        l, ans = Counter(), 0\n",
    "        for i in range(1, len(nums) - 2):\n",
    "            # 到目前为止统计了所有0到i的两坐标和\n",
    "            for j in range(i):\n",
    "                l[nums[i] + nums[j]] += 1\n",
    "            # 目前第三个坐标为i+1，枚举第四个坐标j的范围\n",
    "            for j in range(i + 2, len(nums)):\n",
    "                # 叠加以前统计的左半段和的结果，i+1作为第三个idx和j最多组成这么多\n",
    "                ans += l[nums[j] - nums[i+1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j+1,n):\n",
    "                    for l in range(k+1,n):\n",
    "                        if nums[i]+nums[j]+nums[k]==nums[l]:\n",
    "                            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        return sum(a + b + c == d for a,b,c,d in combinations(nums, 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        特殊四元组数量 = 0\n",
    "        n = len(nums)\n",
    "        for a in range(n-3):\n",
    "            for b in range(a+1, n-2):\n",
    "                for c in range(b+1, n-1):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            特殊四元组数量 += 1\n",
    "        return 特殊四元组数量\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        # nums.sort()\n",
    "        l = nums.__len__()\n",
    "        ans = 0\n",
    "        for i in range(l):\n",
    "            for j in range(i+1, l):\n",
    "                for k in range(j+1, l):\n",
    "                    for z in range(k+1, l):\n",
    "                        if nums[i] + nums[j] + nums[k] == nums[z]:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        cou = 0\n",
    "        for a in range(len(nums)):\n",
    "            for b in range(a+1,len(nums)):\n",
    "                for c in range(b+1,len(nums)):\n",
    "                    for d in range(c+1,len(nums)):\n",
    "                        if nums[a] + nums[b] +nums[c] == nums[d]:\n",
    "                            cou += 1\n",
    "        return cou\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j+1,n):\n",
    "                    for l in range(k,n):\n",
    "                        if nums[i]+nums[j]+nums[k]==nums[l]:\n",
    "                            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(0, n):\n",
    "            for j in range(i+1, n):\n",
    "                for k in range(j+1, n):\n",
    "                    for l in range(k+1, n):\n",
    "                        if (nums[i] + nums[j] + nums[k]) == nums[l]:\n",
    "                            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for a in range(len(nums)):\n",
    "            for b in range(a+1, len(nums)):\n",
    "                for c in range(b+1, len(nums)):\n",
    "                    for d in range(c+1, len(nums)):\n",
    "                        if nums[a] + nums[b] +nums[c] == nums[d]:\n",
    "                            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for c in range(n-2,1,-1):\n",
    "            cnt[nums[c+1]] += 1\n",
    "            for a in range(c):\n",
    "                for b in range(a+1,c):\n",
    "                    if (total := nums[a] + nums[b] + nums[c]) in cnt:\n",
    "                        ans += cnt[total]\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/count-special-quadruplets/solutions/1179031/tong-ji-te-shu-si-yuan-zu-by-leetcode-so-50e2/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(n-3):\n",
    "            for j in range(i+1 , n-2):\n",
    "                for k in range(j+1 , n-1):\n",
    "                    for t in range(k+1 , n):\n",
    "                        if nums[i] + nums[j] + nums[k] == nums[t]:\n",
    "                            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for a in range(len(nums)-3):\n",
    "            for b in range(a +1, len(nums)-2):\n",
    "                for c in range(b +1, len(nums)-1):\n",
    "                    for d in range(c +1, len(nums)):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            ans += 1\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/count-special-quadruplets/solutions/1179031/tong-ji-te-shu-si-yuan-zu-by-leetcode-so-50e2/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a+1,n):\n",
    "                for c in range(b+1,n):\n",
    "                    for d in range(c+1,n):\n",
    "                        if nums[a]+nums[b]+nums[c]==nums[d]:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        count = 0\n",
    "        for i in range(l):\n",
    "            for j in range(i+1, l):\n",
    "                for s in range(j+1, l):\n",
    "                    for t in range(s+1, l):\n",
    "                        if nums[i] + nums[j] + nums[s] == nums[t]:\n",
    "                            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        特殊四元组数量 = 0\n",
    "        n = len(nums)\n",
    "        for a in range(n-3):\n",
    "            for b in range(a+1, n-2):\n",
    "                for c in range(b+1, n-1):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            特殊四元组数量 += 1\n",
    "        return 特殊四元组数量\n",
    "        \"\"\"\n",
    "        #哈希储存\n",
    "        字典 = dict()\n",
    "        字典[nums[0]] = 1\n",
    "        特殊四元组数量 = 0\n",
    "        n = len(nums)\n",
    "        for a in range(1, n-2):\n",
    "            for b in range(a+1, n-1):\n",
    "                for c in range(b+1, n):\n",
    "                    特殊四元组数量 += 字典.get(nums[c]-nums[b]-nums[a], 0)\n",
    "            字典[nums[a]] = 字典.get(nums[a], 0) + 1\n",
    "        return 特殊四元组数量\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        a, b, c, d = 0, 1, 2, 3\n",
    "        result = 0\n",
    "\n",
    "        while a + 4 <= len(nums):\n",
    "            while b + 3 <= len(nums):\n",
    "                while c + 2 <= len(nums):\n",
    "                    while d + 1 <= len(nums):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            result += 1\n",
    "                        d += 1\n",
    "                    c += 1\n",
    "                    d = c + 1\n",
    "                b += 1\n",
    "                c = b + 1\n",
    "                d = c + 1\n",
    "            a += 1\n",
    "            b = a+1\n",
    "            c = b + 1\n",
    "            d = c + 1\n",
    "        return result\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 4:\n",
    "            return False\n",
    "\n",
    "        # 方式一\n",
    "        total = 0\n",
    "        for m in range(3,len(nums)):\n",
    "            for i in range(0,m-2):\n",
    "                for j in range(i + 1,m-1):\n",
    "                    for k in range(j + 1,m):\n",
    "                        if nums[m] == nums[i] + nums[j] + nums[k]:\n",
    "                            total += 1\n",
    "        return total\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for a in range(n-3):\n",
    "            for b in range(a+1, n-2):\n",
    "                for c in range(b+1, n-1):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        for i in range(0,len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                for k in range(j+1,len(nums)):\n",
    "                    for l in range(k+1,len(nums)):\n",
    "                        if nums[i]+nums[j]+nums[k]==nums[l]:\n",
    "                            cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for a in range(n - 3):\n",
    "            for b in range(a + 1, n - 2):\n",
    "                for c in range(b + 1, n - 1):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[0] * 4 for _ in range(101)]\n",
    "        f[0][0] = 1\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            ans += f[nums[i-1]][3]\n",
    "            for j in range(100, -1, -1):\n",
    "                for k in range(4):\n",
    "                    if j - nums[i-1] >= 0 and k - 1 >= 0:\n",
    "                        f[j][k] += f[j - nums[i-1]][k-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-3):\n",
    "            for j in range(i+1, len(nums)-2):\n",
    "                for k in range(j+1, len(nums)-1):\n",
    "                    for l in range(k+1, len(nums)):\n",
    "                        if nums[i] + nums[j] + nums[k] == nums[l]:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        l,ans=Counter(),0\n",
    "        for i in range(1, len(nums)-2):\n",
    "            for j in range(i):\n",
    "                l[nums[i]+nums[j]]+=1\n",
    "            for z in range(i+2,len(nums)):\n",
    "                ans+=l[nums[z]-nums[i+1]]  # d-c,c此时是nums[i+1]\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a+1,n):\n",
    "                for c in range(b+1,n):\n",
    "                    for d in range(c+1,n):\n",
    "                        if nums[a]+nums[b]+nums[c] == nums[d]:\n",
    "                            ans +=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        # 数据量不大？暴力解法\n",
    "        return sum(a + b + c == d for a, b, c, d in combinations(nums, 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        # 数据量不大？四重嵌套！\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n-3):\n",
    "            for b in range(a+1, n-2):\n",
    "                for c in range(b+1, n-1):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for b in range(n - 3, 0, -1):\n",
    "            for d in range(b + 2, n):\n",
    "                cnt[nums[d] - nums[b + 1]] += 1\n",
    "            for a in range(b):\n",
    "                if (total := nums[a] + nums[b]) in cnt:\n",
    "                    ans += cnt[total]\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/count-special-quadruplets/solutions/1179031/tong-ji-te-shu-si-yuan-zu-by-leetcode-so-50e2/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a+1, n):\n",
    "                for c in range(b+1, n):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            count += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        n = len(nums)\n",
    "        for a in range(n):\n",
    "            for b in range(a+1, n):\n",
    "                for c in range(b+1, n):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        res = 0 \n",
    "        n = len(nums)\n",
    "        freq = defaultdict(int)\n",
    "\n",
    "        for i in range(n): \n",
    "            for j in range(i+1, n): # j > i\n",
    "                res += freq[nums[j] - nums[i]]\n",
    "            for k in range(i): # k < i\n",
    "                freq[nums[k] + nums[i]] += 1\n",
    "        \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        特殊四元组数量 = 0\n",
    "        n = len(nums)\n",
    "        for a in range(n-3):\n",
    "            for b in range(a+1, n-2):\n",
    "                for c in range(b+1, n-1):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            特殊四元组数量 += 1\n",
    "        return 特殊四元组数量\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        sum=0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                for k in range(j+1,len(nums)):\n",
    "                    for l in range(k+1,len(nums)):\n",
    "                        if nums[i]+nums[j]+nums[k]==nums[l]:\n",
    "                            sum+=1\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for item in combinations(nums,4):\n",
    "            if item[0] + item[1] + item[2] == item[3]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = defaultdict(int)\n",
    "        for c in range(n - 2, 1, -1):\n",
    "            cnt[nums[c + 1]] += 1\n",
    "            for a in range(c):\n",
    "                for b in range(a + 1, c):\n",
    "                    if (total := nums[a] + nums[b] + nums[c]) in cnt:\n",
    "                        ans += cnt[total]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 4:  \n",
    "            return 0  \n",
    "          \n",
    "        \n",
    "        ans = 0  \n",
    "        for i in range(1, len(nums) - 2): \n",
    "            a = {} \n",
    "            for j in range(i):  \n",
    "                key = nums[i] + nums[j]  \n",
    "                if key not in a:  \n",
    "                    a[key] = 1  \n",
    "                else:  \n",
    "                    a[key] += 1  \n",
    "            for m in range(i + 1, len(nums) - 1):  \n",
    "                for n in range(m + 1, len(nums)):  \n",
    "                    diff = nums[n] - nums[m]  \n",
    "                    if diff in a:  \n",
    "                        ans += a[diff]  \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for b in range(n-3,0,-1):\n",
    "            for d in range(b+2,n):\n",
    "                cnt[nums[d] - nums[b + 1]] += 1\n",
    "            for a in range(b):\n",
    "                if nums[a] + nums[b] in cnt:\n",
    "                    ans += cnt[nums[a] + nums[b]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = 0\n",
    "        for a in range(len(nums)-3):          \n",
    "            for b in range(a+1,len(nums)-2):              \n",
    "                for c in range(b+1,len(nums)-1):       \n",
    "                    for d in range(c+1,len(nums)):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            n += 1\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(n - 3):\n",
    "            for j in range(i + 1, n - 2):\n",
    "                for k in range(j + 1, n - 1):\n",
    "                    for m in range(k + 1, n):\n",
    "                        if nums[i]+nums[j]+nums[k]==nums[m]:\n",
    "                            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        ret += nums[a] + nums[b] + nums[c] == nums[d]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[0] * 4 for _ in range(101)]\n",
    "        f[0][0] = 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += f[nums[i]][3]\n",
    "            for j in range(100, nums[i] - 1, -1):\n",
    "                for k in range(3, 0, -1):\n",
    "                    f[j][k] += f[j - nums[i]][k-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        cnt = Counter()\n",
    "\n",
    "        for b in range(n - 3, 0, -1):\n",
    "\n",
    "            for d in range(b + 2, n):\n",
    "\n",
    "                cnt[nums[d] - nums[b + 1]] += 1\n",
    "            \n",
    "            for a in range(b):\n",
    "\n",
    "                if (total := nums[a] + nums[b] )in cnt:\n",
    "                    res += cnt[total]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for a in range(n):\n",
    "            for b in range(a+1,n):\n",
    "                for c in range(b+1,n):\n",
    "                    for d in range(c+1,n):\n",
    "                        if nums[a]+nums[b]+nums[c]==nums[d]:\n",
    "                            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        count=0\n",
    "        res=[]\n",
    "        for i in range(len(nums)):                        \n",
    "            for j in range(i+1,len(nums)):                                \n",
    "                for k in range(j+1,len(nums)):                           \n",
    "                    for m in range(k+1,len(nums)):\n",
    "                        if nums[i]+nums[j]+nums[k]==nums[m]:                        \n",
    "                            count+=1\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[0] * 4 for _ in range(101)]\n",
    "        f[0][0] = 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += f[nums[i]][3]\n",
    "            for j in range(100, -1, -1):\n",
    "                for k in range(4):\n",
    "                    if j - nums[i] >= 0 and k - 1 >= 0:\n",
    "                        f[j][k] += f[j - nums[i]][k-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for c in range(n):\n",
    "            for d in range(c+1, n):\n",
    "                ans += cnt[nums[d] - nums[c]]\n",
    "            b = c\n",
    "            for a in range(b):\n",
    "                cnt[nums[a] + nums[b]] += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        count = 0\n",
    "        for i in range(l):\n",
    "            for j in range(i+1, l):\n",
    "                for s in range(j+1, l):\n",
    "                    for t in range(s+1, l):\n",
    "                        if nums[i] + nums[j] + nums[s] == nums[t]:\n",
    "                            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        res = 0 \n",
    "        n = len(nums)\n",
    "        freq = defaultdict(int)\n",
    "        for i in range(n): \n",
    "            for j in range(i+1, n): # j > i\n",
    "                res += freq[nums[j] - nums[i]]\n",
    "            for k in range(i): # k < i\n",
    "                freq[nums[k] + nums[i]] += 1\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a + 1, n):\n",
    "                for c in range(b + 1, n):\n",
    "                    for d in range(c + 1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        # ans=0\n",
    "        # for a in range(n):\n",
    "        #     for b in range(a+1,n):\n",
    "        #         for c in range(b+1,n):\n",
    "        #             for d in range(c+1,n):\n",
    "        #                 if nums[a]+nums[b]+nums[c]==nums[d]:\n",
    "        #                     ans+=1\n",
    "        # return ans\n",
    "        \n",
    "        ans = 0 \n",
    "        n = len(nums)\n",
    "        freq=defaultdict(int)\n",
    "        for b in range(n-3,0,-1):\n",
    "            c=b+1\n",
    "            for d in range(c+1,n):\n",
    "                freq[nums[d]-nums[c]]+=1\n",
    "            for a in range(b):\n",
    "                ans+=freq[nums[a]+nums[b]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(len(nums)):\r\n",
    "            for j in range(i+1,len(nums)):\r\n",
    "                for k in range(j+1,len(nums)):\r\n",
    "                    for l in range(k+1,len(nums)):\r\n",
    "                        if nums[i] + nums[j] + nums[k] == nums[l]:\r\n",
    "                            ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a+1, n):\n",
    "                for c in range(b+1, n):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            count += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for a in range(n):\n",
    "            for b in range(a+1,n):\n",
    "                for c in range(b+1,n):\n",
    "                    for d in range(c+1,n):\n",
    "                        if nums[a]+nums[b]+nums[c] == nums[d]:\n",
    "                            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        counter =  {}\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for b in range(n-2, 0, -1):\n",
    "            for d in range(b+2, n):\n",
    "                d_c = nums[d]-nums[b+1]\n",
    "                counter[d_c] = counter.get(d_c, 0) + 1\n",
    "            for a in range(b):\n",
    "                res += counter.get(nums[a] + nums[b], 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 3):\n",
    "            for j in range(i + 1, len(nums) - 2):\n",
    "                for k in range(j + 1, len(nums) - 1):\n",
    "                    for f in range(k + 1, len(nums)):\n",
    "                        if nums[i] + nums[j] + nums[k] == nums[f]:\n",
    "                            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        特殊四元组数量 = 0\n",
    "        n = len(nums)\n",
    "        for a in range(n-3):\n",
    "            for b in range(a+1, n-2):\n",
    "                for c in range(b+1, n-1):\n",
    "                    for d in range(c+1, n):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            特殊四元组数量 += 1\n",
    "        return 特殊四元组数量\n",
    "        \"\"\"\n",
    "        #哈希储存\n",
    "        字典 = dict()\n",
    "        字典[nums[0]] = 1\n",
    "        特殊四元组数量 = 0\n",
    "        n = len(nums)\n",
    "        for a in range(1, n-2):\n",
    "            for b in range(a+1, n-1):\n",
    "                for c in range(b+1, n):\n",
    "                    特殊四元组数量 += 字典.get(nums[c]-nums[b]-nums[a], 0)\n",
    "            字典[nums[a]] = 字典.get(nums[a], 0) + 1\n",
    "        return 特殊四元组数量\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        count=0\n",
    "        for a in range(len(nums)-3):\n",
    "            for b in range(a+1,len(nums)-2):\n",
    "                for c in range(b+1,len(nums)-1):\n",
    "                    for d in range(c+1,len(nums)):\n",
    "                        if nums[a] + nums[b] + nums[c] == nums[d]:\n",
    "                            count+=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        cal=0\n",
    "        for i in range (len(nums)-3):\n",
    "            for j in range (i+1,len(nums)-2):\n",
    "                for k in range(j+1,len(nums)-1):\n",
    "                    sum = nums[i]+nums[j]+nums[k]\n",
    "                    for m in range (k,len(nums)):\n",
    "                        if sum == nums[m] :\n",
    "                            cal += 1\n",
    "        return cal\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j+1,n):\n",
    "                    for p in range(k+1,n):\n",
    "                        if nums[i]+nums[j]+nums[k]==nums[p]:\n",
    "                            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        sum=0\n",
    "        m=len(nums)\n",
    "        for i in range(m):\n",
    "            for j in range(i+1,m):\n",
    "                for k in range (j+1,m):\n",
    "                    for l in range(k+1,m):\n",
    "                        if nums[i] + nums[j] + nums[k] == nums[l] :\n",
    "                            sum+=1\n",
    "        return sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        # 数据量不大？暴力解法\n",
    "        ans = 0\n",
    "        for a, b, c, d in combinations(nums, 4):\n",
    "            if a + b + c == d:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        def backtrace(path, start):\n",
    "            nonlocal ans\n",
    "            if len(path) == 4:\n",
    "                if path[0] + path[1] + path[2] == path[3]:\n",
    "                    ans += 1\n",
    "                return\n",
    "            for i in range(start, nums_len):\n",
    "                path.append(nums[i])\n",
    "                backtrace(path, i+1)\n",
    "                path.pop()\n",
    "\n",
    "        ans = 0\n",
    "        nums_len = len(nums)\n",
    "        backtrace([], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for p in range(j + 1, n):\n",
    "                    for q in range(p + 1, n):\n",
    "                        if nums[i] + nums[j] + nums[p] == nums[q]:\n",
    "                            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        nums_idx = {v: key for key, v in enumerate(nums)}\n",
    "        print(nums_idx)\n",
    "        nums_l = len(nums)\n",
    "        result = 0\n",
    "        for i in range(nums_l - 3):\n",
    "            for j in range(i +1, nums_l - 2):\n",
    "                for k in range(j + 1, nums_l - 1):\n",
    "                    tmp = nums[i] + nums[j] + nums[k]\n",
    "                    if tmp in nums_idx:\n",
    "                        result += nums[k+1:].count(tmp)\n",
    "                            \n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
